#![allow(dead_code, mutable_transmutes, non_camel_case_types, non_snake_case, non_upper_case_globals, unused_assignments, unused_mut)]
use std::mem;
use crate::alloc_testing::*;
extern "C" {
    fn memcpy(
        _: *mut libc::c_void,
        _: *const libc::c_void,
        _: libc::c_ulong,
    ) -> *mut libc::c_void;
            }
pub type size_t = libc::c_ulong;
pub type BinomialHeapType = libc::c_uint;
pub const BINOMIAL_HEAP_TYPE_MAX: BinomialHeapType = 1;
pub const BINOMIAL_HEAP_TYPE_MIN: BinomialHeapType = 0;
pub type BinomialHeapValue = *mut libc::c_void;
pub type BinomialHeapCompareFunc = Option::<
    unsafe extern "C" fn(BinomialHeapValue, BinomialHeapValue) -> libc::c_int,
>;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _BinomialHeap {
    pub heap_type: BinomialHeapType,
    pub compare_func: BinomialHeapCompareFunc,
    pub num_values: libc::c_uint,
    pub roots: *mut *mut BinomialTree,
    pub roots_length: libc::c_uint,
}
pub type BinomialTree = _BinomialTree;
#[derive(Copy, Clone)]
#[repr(C)]
pub struct _BinomialTree {
    pub value: BinomialHeapValue,
    pub order: libc::c_ushort,
    pub refcount: libc::c_ushort,
    pub subtrees: *mut *mut BinomialTree,
}
pub type BinomialHeap = _BinomialHeap;
extern "C" fn binomial_heap_cmp(
    mut heap: *mut BinomialHeap,
    mut data1: BinomialHeapValue,
    mut data2: BinomialHeapValue,
) -> libc::c_int {
    let boxed_heap = unsafe { Box::from_raw(heap) };
    let heap_type = boxed_heap.heap_type;
    let compare_func = boxed_heap.compare_func.expect("non-null function pointer");

    let result = if heap_type as libc::c_uint == BINOMIAL_HEAP_TYPE_MIN as libc::c_int as libc::c_uint {
        unsafe { compare_func(data1, data2) }
    } else {
        -unsafe { compare_func(data1, data2) }
    };

    heap = Box::into_raw(boxed_heap);
    result
}
extern "C" fn binomial_tree_ref(mut tree: *mut BinomialTree) {
    if !tree.is_null() {
        let mut boxed_tree = unsafe { Box::from_raw(tree) };
        boxed_tree.refcount = boxed_tree.refcount.wrapping_add(1);
        tree = Box::into_raw(boxed_tree);
    }
}
extern "C" fn binomial_tree_unref(mut tree: *mut BinomialTree) {
    if tree.is_null() {
        return;
    }

    let mut boxed_tree = unsafe { Box::from_raw(tree) };
    boxed_tree.refcount = boxed_tree.refcount.wrapping_sub(1);
    if boxed_tree.refcount == 0 {
        let mut i: libc::c_int = 0;
        while i < boxed_tree.order as libc::c_int {
            binomial_tree_unref(unsafe { *boxed_tree.subtrees.offset(i as isize) });
            i += 1;
        }
        alloc_test_free(boxed_tree.subtrees as *mut libc::c_void);
        alloc_test_free(tree as *mut libc::c_void);
    }
    let tree = Box::into_raw(boxed_tree);
}
extern "C" fn binomial_tree_merge(
    mut heap: *mut BinomialHeap,
    mut tree1: *mut BinomialTree,
    mut tree2: *mut BinomialTree,
) -> *mut BinomialTree {
    let mut new_tree: *mut BinomialTree = std::ptr::null_mut();
    let mut tmp: *mut BinomialTree = std::ptr::null_mut();
    let mut i: libc::c_int = 0;

    unsafe {
        if binomial_heap_cmp(heap, (*tree1).value, (*tree2).value) > 0 {
            tmp = tree1;
            tree1 = tree2;
            tree2 = tmp;
        }
    }

    new_tree = unsafe {
        alloc_test_malloc(std::mem::size_of::<BinomialTree>() as libc::c_ulong)
            as *mut BinomialTree
    };
    if new_tree.is_null() {
        return std::ptr::null_mut();
    }

    unsafe {
        (*new_tree).refcount = 0;
        (*new_tree).order = ((*tree1).order as libc::c_int + 1) as libc::c_ushort;
        (*new_tree).value = (*tree1).value;
    }

    let subtrees = unsafe {
        alloc_test_malloc(
            (std::mem::size_of::<*mut BinomialTree>() as libc::c_ulong)
                .wrapping_mul((*new_tree).order as libc::c_ulong),
        ) as *mut *mut BinomialTree
    };
    if subtrees.is_null() {
        unsafe {
            alloc_test_free(new_tree as *mut libc::c_void);
        }
        return std::ptr::null_mut();
    }

    unsafe {
        std::ptr::copy_nonoverlapping(
            (*tree1).subtrees as *const libc::c_void,
            subtrees as *mut libc::c_void,
            (std::mem::size_of::<*mut BinomialTree>() as libc::c_ulong)
                .wrapping_mul((*tree1).order as libc::c_ulong)
                .try_into().unwrap(),
        );
        *subtrees.offset(((*new_tree).order as libc::c_int - 1) as isize) = tree2;
        (*new_tree).subtrees = subtrees;
    }

    i = 0;
    while i < unsafe { (*new_tree).order } as libc::c_int {
        unsafe {
            binomial_tree_ref(*((*new_tree).subtrees).offset(i as isize));
        }
        i += 1;
    }

    new_tree
}
extern "C" fn binomial_heap_merge_undo(
    mut new_roots: *mut *mut BinomialTree,
    mut count: libc::c_uint,
) {
    let mut i: libc::c_uint = 0;
    while i <= count {
        unsafe {
            binomial_tree_unref(*new_roots.offset(i as isize));
        }
        i = i.wrapping_add(1);
    }
    unsafe {
        alloc_test_free(new_roots as *mut libc::c_void);
    }
}
extern "C" fn binomial_heap_merge(
    mut heap: *mut BinomialHeap,
    mut other: *mut BinomialHeap,
) -> libc::c_int {
    let mut new_roots: *mut *mut BinomialTree = std::ptr::null_mut();
    let mut new_roots_length: libc::c_uint = 0;
    let mut vals: [*mut BinomialTree; 3] = [std::ptr::null_mut(); 3];
    let mut num_vals: libc::c_int = 0;
    let mut carry: *mut BinomialTree = std::ptr::null_mut();
    let mut new_carry: *mut BinomialTree = std::ptr::null_mut();
    let mut max: libc::c_uint = 0;
    let mut i: libc::c_uint = 0;

    let mut boxed_heap = unsafe { Box::from_raw(heap) };
    let mut boxed_other = unsafe { Box::from_raw(other) };

    if boxed_heap.roots_length > boxed_other.roots_length {
        max = boxed_heap.roots_length.wrapping_add(1);
    } else {
        max = boxed_other.roots_length.wrapping_add(1);
    }

    new_roots = unsafe {
        alloc_test_malloc(
            (std::mem::size_of::<*mut BinomialTree>() as libc::c_ulong)
                .wrapping_mul(max as libc::c_ulong),
        ) as *mut *mut BinomialTree
    };

    if new_roots.is_null() {
        heap = Box::into_raw(boxed_heap);
        other = Box::into_raw(boxed_other);
        return 0;
    }

    new_roots_length = 0;
    carry = std::ptr::null_mut();
    i = 0;

    while i < max {
        num_vals = 0;

        if i < boxed_heap.roots_length && !unsafe { *boxed_heap.roots.offset(i as isize) }.is_null() {
            vals[num_vals as usize] = unsafe { *boxed_heap.roots.offset(i as isize) };
            num_vals += 1;
        }
        if i < boxed_other.roots_length && !unsafe { *boxed_other.roots.offset(i as isize) }.is_null() {
            vals[num_vals as usize] = unsafe { *boxed_other.roots.offset(i as isize) };
            num_vals += 1;
        }

        if !carry.is_null() {
            vals[num_vals as usize] = carry;
            num_vals += 1;
        }

        if num_vals & 1 != 0 {
            unsafe {
                let ref mut fresh1 = *new_roots.offset(i as isize);
                *fresh1 = vals[(num_vals - 1) as usize];
                binomial_tree_ref(*new_roots.offset(i as isize));
            }
            new_roots_length = i.wrapping_add(1);
        } else {
            unsafe {
                let ref mut fresh2 = *new_roots.offset(i as isize);
                *fresh2 = std::ptr::null_mut();
            }
        }

        if num_vals & 2 != 0 {
            new_carry = unsafe { binomial_tree_merge(heap, vals[0], vals[1]) };
            if new_carry.is_null() {
                binomial_heap_merge_undo(new_roots, i);
                binomial_tree_unref(carry);
                heap = Box::into_raw(boxed_heap);
                other = Box::into_raw(boxed_other);
                return 0;
            }
        } else {
            new_carry = std::ptr::null_mut();
        }

        binomial_tree_unref(carry);
        carry = new_carry;
        binomial_tree_ref(carry);
        i = i.wrapping_add(1);
    }

    i = 0;

    while i < boxed_heap.roots_length {
        if !unsafe { *boxed_heap.roots.offset(i as isize) }.is_null() {
            binomial_tree_unref(unsafe { *boxed_heap.roots.offset(i as isize) });
        }
        i = i.wrapping_add(1);
    }

    unsafe {
        alloc_test_free(boxed_heap.roots as *mut libc::c_void);
        boxed_heap.roots = new_roots;
        boxed_heap.roots_length = new_roots_length;
    }

    heap = Box::into_raw(boxed_heap);
    other = Box::into_raw(boxed_other);
    return 1;
}
#[no_mangle]
pub extern "C" fn binomial_heap_new(
    heap_type: BinomialHeapType,
    compare_func: BinomialHeapCompareFunc,
) -> *mut BinomialHeap {
    let new_heap: *mut BinomialHeap = unsafe {
        alloc_test_calloc(
            1,
            std::mem::size_of::<BinomialHeap>().try_into().unwrap(),
        ) as *mut BinomialHeap
    };

    if new_heap.is_null() {
        return std::ptr::null_mut();
    }

    let mut boxed_heap = unsafe { Box::from_raw(new_heap) };
    boxed_heap.heap_type = heap_type;
    boxed_heap.compare_func = compare_func;
    let new_heap = Box::into_raw(boxed_heap);

    new_heap
}
#[no_mangle]
pub extern "C" fn binomial_heap_free(mut heap: *mut BinomialHeap) {
    if !heap.is_null() {
        let boxed_heap = unsafe { Box::from_raw(heap) };
        let mut i: libc::c_uint = 0;
        while i < boxed_heap.roots_length {
            unsafe {
                binomial_tree_unref(*boxed_heap.roots.offset(i as isize));
            }
            i = i.wrapping_add(1);
        }
        alloc_test_free(boxed_heap.roots as *mut libc::c_void);
        alloc_test_free(heap as *mut libc::c_void);
        let heap = Box::into_raw(boxed_heap);
    }
}
#[no_mangle]
pub extern "C" fn binomial_heap_insert(
    mut heap: *mut BinomialHeap,
    mut value: BinomialHeapValue,
) -> libc::c_int {
    let mut fake_heap: BinomialHeap = _BinomialHeap {
        heap_type: BINOMIAL_HEAP_TYPE_MIN,
        compare_func: None,
        num_values: 0,
        roots: std::ptr::null_mut(),
        roots_length: 0,
    };
    let mut new_tree: *mut BinomialTree = std::ptr::null_mut();
    let mut result: libc::c_int = 0;

    new_tree = alloc_test_malloc(std::mem::size_of::<BinomialTree>() as libc::c_ulong)
        as *mut BinomialTree;
    if new_tree.is_null() {
        return 0;
    }
    let mut boxed_new_tree = unsafe { Box::from_raw(new_tree) };
    boxed_new_tree.value = value;
    boxed_new_tree.order = 0;
    boxed_new_tree.refcount = 1;
    boxed_new_tree.subtrees = std::ptr::null_mut();
    new_tree = Box::into_raw(boxed_new_tree);

    let mut boxed_heap = unsafe { Box::from_raw(heap) };
    fake_heap.heap_type = boxed_heap.heap_type;
    fake_heap.compare_func = boxed_heap.compare_func;
    fake_heap.num_values = 1;
    fake_heap.roots = &mut new_tree;
    fake_heap.roots_length = 1;
    result = binomial_heap_merge(heap, &mut fake_heap);
    if result != 0 {
        boxed_heap.num_values = boxed_heap.num_values.wrapping_add(1);
    }
    heap = Box::into_raw(boxed_heap);

    binomial_tree_unref(new_tree);

    result
}
#[no_mangle]
pub extern "C" fn binomial_heap_pop(
    mut heap: *mut BinomialHeap,
) -> BinomialHeapValue {
    let mut least_tree: *mut BinomialTree = std::ptr::null_mut();
    let mut fake_heap: BinomialHeap = _BinomialHeap {
        heap_type: BINOMIAL_HEAP_TYPE_MIN,
        compare_func: None,
        num_values: 0,
        roots: std::ptr::null_mut(),
        roots_length: 0,
    };
    let mut result: BinomialHeapValue = std::ptr::null_mut();
    let mut i: libc::c_uint = 0;
    let mut least_index: libc::c_uint = 0;

    
    unsafe {
        if (*heap).num_values == 0 {
            return std::ptr::null_mut();
        }

        least_index = (2147483647 as libc::c_int as libc::c_uint)
            .wrapping_mul(2)
            .wrapping_add(1);
        i = 0;
        while i < (*heap).roots_length {
            if !(*((*heap).roots).offset(i as isize)).is_null() {
                if least_index
                    == (2147483647 as libc::c_int as libc::c_uint)
                        .wrapping_mul(2)
                        .wrapping_add(1)
                    || binomial_heap_cmp(
                        heap,
                        (**((*heap).roots).offset(i as isize)).value,
                        (**((*heap).roots).offset(least_index as isize)).value,
                    ) < 0
                {
                    least_index = i;
                }
            }
            i = i.wrapping_add(1);
        }

        least_tree = *((*heap).roots).offset(least_index as isize);
        let ref mut fresh3 = *((*heap).roots).offset(least_index as isize);
        *fresh3 = std::ptr::null_mut();
        fake_heap.heap_type = (*heap).heap_type;
        fake_heap.compare_func = (*heap).compare_func;
        fake_heap.roots = (*least_tree).subtrees;
        fake_heap.roots_length = (*least_tree).order as libc::c_uint;
    }

    if unsafe { binomial_heap_merge(heap, &mut fake_heap) } != 0 {
        result = unsafe { (*least_tree).value };
        unsafe { binomial_tree_unref(least_tree) };
        unsafe {
            (*heap).num_values = (*heap).num_values.wrapping_sub(1);
        }
        return result;
    } else {
        unsafe {
            let ref mut fresh4 = *((*heap).roots).offset(least_index as isize);
            *fresh4 = least_tree;
        }
        return std::ptr::null_mut();
    }
}
#[no_mangle]
pub extern "C" fn binomial_heap_num_entries(
    mut heap: *mut BinomialHeap,
) -> libc::c_uint {
    if heap.is_null() {
        return 0;
    }
    let boxed_heap = unsafe { Box::from_raw(heap) };
    let num_values = boxed_heap.num_values;
    heap = Box::into_raw(boxed_heap);
    num_values
}
